package org.hot100.h207;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wjy
 * @Date: 2022/2/9 14:46
 */
public class Solution {

    public static void main(String[] args) {

        int[][] ints = {
                {5, 3},
                {5, 4},
                {3, 0},
                {3, 1},
                {4, 1},
                {4, 2}
        };

        Solution solution = new Solution();
        System.out.println(solution.canFinish(6, ints));

    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        // 保存课程号及课程号对应先修课程号
        List<List<Integer>> lists = new ArrayList<>();

        // 给每节课的前修课都进行初始化
        for (int i = 0; i < numCourses; i++) {
            lists.add(new ArrayList<>());
        }
        
        // 记录课程状态
        int[] courses = new int[numCourses];

        // 将前修课号对应后修课的课号放入集合中
        for (int[] ints : prerequisites) {
            lists.get(ints[1]).add(ints[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, courses, lists)) {
                return false;
            }
        }

        return true;
    }

    public boolean dfs(int numCourse, int[] courses, List<List<Integer>> lists) {
        if (courses[numCourse] == 1) {
            return false;
        }
        if (courses[numCourse] == -1) {
            return true;
        }

        courses[numCourse] = 1;

        // 获取先修课程对应的后修课程
        for (int i : lists.get(numCourse)) {
            if (!dfs(i, courses, lists)) {
                return false;
            }
        }

        courses[numCourse] = -1;
        return true;
    }

}
